package com.cdream.basic.algorithm.leetcode.bfs;


public class Offer13 {
    int count = 0;
    boolean[][] used;

    public int movingCount(int m, int n, int k) {
        used = new boolean[m][n];
        dfs(0, 0, k);
        return count;

    }

    private void dfs(int i, int j, int k) {
        if (i < 0 || j < 0 || i >= used.length || j >= used[0].length || (bitSum(i) + bitSum(j) > k)) {
            return;
        }
        if (used[i][j]) {
            return;
        }
        used[i][j] = true;
        count++;
        dfs(i + 1, j, k);
        dfs(i - 1, j, k);
        dfs(i, j + 1, k);
        dfs(i, j - 1, k);

    }

    private int bitSum(int num) {
        int sum = 0;
        while (num != 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(new Offer13().movingCount(16, 8, 4));
    }
}
